package 动态规划;

public class 最长回文子串 {
    public String longestPalindrome(String s) {
        int len = s.length();
        int[][] dp = new int[len][len];
        int max = 0;
        int k = 0;
        String r = new StringBuffer(s).reverse().toString();
        for (int i = 0 ; i < len ; i ++){
            for (int j = 0 ; j < len ; j ++){
                if (s.charAt(i) == r.charAt(j)){
                    if (i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                }
                if (dp[i][j] > max){
                    if (len - 1 - j + dp[i][j] - 1 == i){
                        max = dp[i][j];
                        k = i;
                    }
                }
            }

        }
        return s.substring(k + 1 - max , k + 1);
    }

}
